#include <iostream>
#include <vector>

using namespace std;

/**
  * @方法: 贪心。及时种花。如不新建数组的话，会破坏原数组。
  * @时间复杂度: o(n)
  * @空间复杂度: o(n) 或 o(1)
  * @评价: 若破坏原数组，空间为 o(1)
*/
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    vector<int> myfb(flowerbed);
    int maxFlowers = 0;
    for(int i=0;i<myfb.size();i++){
        if(myfb[i] == 0 && (i==0 || myfb[i-1] == 0) && (i==myfb.size()-1 || myfb[i+1] == 0)){
            maxFlowers++;
            myfb[i] = 1;
        }
    }
    if(n <= maxFlowers) return true;
    return false;
}

/**
  * @方法: 统计每两个1之间的0数，并且根据数组大小，具体算出最多可种多少花
  * @时间复杂度: o(n)
  * @空间复杂度: o(|z|) 其中 |z| 为总共的间隔数。
  * @评价: lsc 的解法
*/
bool canPlaceFlowers1(vector<int>& flowerbed, int n) {
    vector<int> blank;
    int cnt=0;
    for(int i=0;i<flowerbed.size();i++){
        if(flowerbed[i] == 1){
            blank.push_back(cnt);
            cnt = 0;
        }else {
            cnt++;
        }
    }
    blank.push_back(cnt);
    int maxFlowers = 0;
    if(blank.size() == 1){
        maxFlowers = (blank[0]+1) / 2;
    }else{
        for(int i=1;i<blank.size()-1;i++){
            maxFlowers += (blank[i]-1) / 2;
        }
        maxFlowers = maxFlowers + blank[0] / 2 + blank[blank.size()-1] / 2;
    }
    if(n <= maxFlowers) return true;
    return false;
}

int main() {
    cout << "hello world" << endl;
    vector<int> ff = {1,0,0,0,0,1};
    canPlaceFlowers(ff, 2);

    return 0;
}